package com.iweb;

/**
 * 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * 请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * <p>
 * 示例1：
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * <p>
 * 示例2：
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.5
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 */
public class Solution1 {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int len1 = nums1.length;
        int len2 = nums2.length;

        if (len1 == 0 && len2 == 0) return 0.0; // 两个数组为0的情况

        int len = len1 + len2; // 数组的总长度

        boolean flag = len % 2 == 1; // 定义一个标记表示合并后数组的长度是奇数还是偶数
        // 中位数的索引位置,根据奇数还是偶数
        int mid = flag ? (len - 1) / 2 : len / 2;
        int[] arr = new int[mid + 1]; // 定义一个临时数组
        int k = 0; // 临时数组的位置

        int x = 0, y = 0; // 两个指针

        // 比较相同长度位置的数组
        while (x < len1 && y < len2 && k <= mid) {
            // 将比较后小的数组元素存放临时数组中
            if (nums1[x] <= nums2[y]) {
                arr[k++] = nums1[x++];
            } else {
                arr[k++] = nums2[y++];
            }
        }

        // 剩余的 nums1
        while (x < len1 && k <= mid) {
            arr[k++] = nums1[x++];
        }

        // 剩余的 nums2
        while (y < len2 && k <= mid) {
            arr[k++] = nums2[y++];
        }

        // 中位数的计算根据奇数还是偶数
        return flag ? arr[mid] : (arr[mid] + arr[mid - 1]) / 2.0;
    }


    public static void main(String[] args) {

        int[] nums1 = {1};
        int[] nums2 = {2, 4, 6, 8};

        System.out.println(findMedianSortedArrays(nums1, nums2));

    }
}
